package leetcode.editor.day;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;

// 857. 雇佣 K 名工人的最低成本
// https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/
class MinimumCostToHireKWorkers {
    public static void main(String[] args) {
        Solution solution = new MinimumCostToHireKWorkers().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 首先证明，对于选择的工人组，需要支付的工资为 工作量之和 * （最低工资/工作量）的最大值
        // 记 wage[i]/quality[i] 为 ratio[i] 则有 sum{quality_i} * max{ratio_i}
        // 按照ratio排序，从小到大来枚举，求数组每个前缀的前k-1小元素之和（对于每个作为最高ratio的人，选出k-1个工作量低的人与之配对）
        // 先将排序好的数组中 k - 1 个元素放入，后面的再进行模拟，每次踢出一个quality[i]最大值
        // 参照官解：https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/solution/gu-yong-k-ming-gong-ren-de-zui-di-cheng-rsz3t/
        public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
            int n = quality.length;
            Integer[] h = new Integer[n];
            for (int i = 0; i < n; i++) {
                h[i] = i;
            }

            // 按照 quality[i] / wage[i] 权重进行排序
            Arrays.sort(h, (a, b) -> quality[b] * wage[a] - quality[a] * wage[b]);

            // 质量的总和
            double totalq = 0.0, res = 1e9;
            PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
            // 最少都需要 k 个，所以先将前面权重较小的 k - 1 个入队
            for (int i = 0; i < k - 1; i++) {
                totalq += quality[h[i]];
                queue.offer(quality[h[i]]);
            }

            for (int i = k - 1; i < n; i++) {
                int idx = h[i];
                totalq += quality[idx];
                queue.offer(quality[idx]);
                // 求总共需要最小工资，此时只要满足k得到最小工资，前面的都满足
                double totalc = ((double) wage[idx] / quality[idx]) * totalq;
                res = Math.min(totalc, res);
                // 减去最大质量的那个工人，根据 wage[i] / quality[i]，干的多的，工资反而需要发的更多，所以去掉优先级队列中最大的
                // 通俗地说：就是踢出一个干活多的。为了少付钱，我们不需要你干活，凑够人数撑场面就行了。
                // 减去之后继续模拟下一个
                totalq -= queue.poll();
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
